using System;
using System.Collections.Generic;
using System.Text;

namespace graph
{
    enum NodeType {NormalNode, QueryNode, EvidenceNode};    

    class Node
    {
        public String Name;
        public NodeType Type;
        public List<Node> Parents = new List<Node>();
        public List<Node> Children = new List<Node>();
    }

    class Graph
    {
        public String Name;
        public Dictionary<String, Node> Nodes = new Dictionary<String,Node>();
        public Dictionary<String, Node> QueryNodes = new Dictionary<String, Node>();
        public Dictionary<String, Node> EvidenceNodes = new Dictionary<String, Node>();

        // This function will clean out links to nodes not in graph
        public void Repair()
        {
            // First step let's get rid of non-existing nodes in QueryNodes and EvidenceNodes
            List<String> Nodes2Remove = new List<string>();
            foreach (Node n in EvidenceNodes.Values)
            {
                if (!Nodes.ContainsKey(n.Name))
                {
                    Nodes2Remove.Add(n.Name);
                }
            }
            foreach (String s in Nodes2Remove)
            {
                EvidenceNodes.Remove(s);
            }
            Nodes2Remove.Clear();

            // Let's clean up the hanging links now
            foreach (Node n in Nodes.Values)
            {
                for (int i = n.Parents.Count - 1; i >= 0; i--)
                {
                    if (!Nodes.ContainsKey(n.Parents[i].Name))
                    {
                        n.Parents.RemoveAt(i);
                    }
                }
                for (int i = n.Children.Count - 1; i >= 0; i--)
                {
                    if (!Nodes.ContainsKey(n.Children[i].Name))
                    {
                        n.Children.RemoveAt(i);
                    }
                }
            }
            foreach (Node n in Nodes.Values)
            {
                if (n.Parents.Count == 0 && n.Children.Count == 0 && n.Type != NodeType.QueryNode)
                {
                    Nodes2Remove.Add(n.Name);
                }
            }
            foreach (String s in Nodes2Remove)
            {
                Nodes.Remove(s);
            }
            Nodes2Remove = null;
        }
    }
}
